(파이썬 S/W 문제해결 기본) String - 4864번 4861번 4865번

4864번 - 문자열 비교

• 시간 : 10개 테스트케이스를 합쳐서 Python의 경우 2초
• 메모리 : 힙, 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내

보이어 무어 알고리즘 활용

def boyer_moore(pattern, text):
result = 0
pivot = len(pattern)-1
skip = list(pattern)
skip.reverse()

    while result!=1 and pivot<len(text):
        if pattern[len(pattern) - 1] != text[pivot]:
            if text[pivot] in skip:
                nums = skip.index(text[pivot])
                pivot += nums
            else:
                pivot += len(pattern)
        else:
            for i, j in zip(range(pivot, pivot - len(pattern), -1), skip):
                if text[i] == j:
                    result = 1
                else:
                    result = 0
                    pivot = i
                    break
    return result

T = int(input())

for test_case in range(1, T+1):
str1 = input()
str2 = input()

    print('#{} {}'.format(test_case, boyer_moore(str1, str2)))

---

4861번 - 회문

• 시간 : 10개 테스트케이스를 합쳐서 Python의 경우 2초
• 메모리 : 힙, 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내

2차원 리스트 다루는게 아직 익숙하지 않다

TC = int(input())

for tc in range(1, TC+1):
N, M = map(int, input().split())
result = []

    #가로줄 확인
    Garo_lst = []
    for i in range(N):
        Data = input()
        Garo_lst.append(Data)
        for i in range(len(Data)-M+1):
            if Data[i:M+i] == Data[i:M+i][::-1]:
                result.append(Data[i:M+i])

    #세로줄 확인
    Sero_lst = []
    Sero_sub_lst = ''
    for x in range(N):
        for y in Garo_lst:
            Sero_sub_lst += y[x]
        Sero_lst.append(Sero_sub_lst)
        Sero_sub_lst =''
    print(Sero_lst)

    for sero_data in Sero_lst:
        for j in range(len(sero_data)-M+1):
            if sero_data[j:M+j] == sero_data[j:M+j][::-1]:
                result.append(sero_data[j:M+j])

    # print(result)
    print("#%d %s"%(tc, result[0]))

---

4865번 - 글자수

• 시간 : 10개 테스트케이스를 합쳐서 Python의 경우 2초
• 메모리 : 힙, 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내

T = int(input())

for test_case in range(1, T+1):
str1 = input()
str2 = input()
cnt, max_cnt = 0, 0

    for i in str1:
        for j in str2:
            if i == j:
                cnt += 1
        if cnt > max_cnt:
            max_cnt = cnt
        cnt = 0

    print('#{} {}'.format(test_case, max_cnt))